package quwei;

import java.util.Scanner;
//最小生成树
public class Test2_7 {

    static final int INF=0x3fffffff;
    static final int N=100;
    static boolean[] s=new boolean[N];                         //s[i]=true，说明顶点i已加入集合U中
    static int[] closest=new int[N];                           //表示集合V-U中顶点j到U集合的最邻近顶点
    static int[] lowcost=new int[N];                           //表示集合V-U中顶点j到U集合的最邻近距离

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("输入结点数n和边数m：");
        int n=scanner.nextInt();
        int m=scanner.nextInt();
        int[][] c=new int[n+1][n+1];                            //存放图的权值

        for(int i=1;i<=n;i++) {                                 //初始化邻接矩阵
            for(int j=1;j<=n;j++)
                c[i][j]=INF;
        }
        System.out.println("输入结点数u、v和边值w：");
        int u,v,w;
        for(int i=1;i<=m;i++) {
            u=scanner.nextInt();
            v=scanner.nextInt();
            w=scanner.nextInt();
            c[u][v]=c[v][u]=w;
        }
        System.out.println("输入任一结点u0：");
        int u0=scanner.nextInt();

        Prim(n,u0,c);                                           //求最小权值之和
        int sumcost=0;
        System.out.println("数组lowcost的内容为：");
        for(int i=1;i<=n;i++) {
            System.out.print(lowcost[i]+" ");
            sumcost+=lowcost[i];
        }
        System.out.println("最小的花费是："+sumcost);
        scanner.close();
    }

    public static void Prim(int n,int u0,int[][] c) {
        s[u0]=true;                                             //初始时集合U中只有一个元素即u0
        for(int i=1;i<=n;i++) {                                 //初始化closest、lowcost和s数组
            if(i!=u0) {
                lowcost[i]=c[u0][i];
                closest[i]=u0;
                s[i]=false;                                     //除u0外其他顶点都不在集合U中
            }
            else
                lowcost[i]=0;
        }

        for(int i=1;i<=n;i++) {
            int temp=INF;
            int t=u0;
            for(int j=1;j<=n;j++) {                             //在集合V-U中寻找距离集合U最近的顶点t
                if(!s[j]&&lowcost[j]<temp) {                    //!s[j]说明j顶点在V-U中
                    t=j;
                    temp=lowcost[j];
                }
            }
            s[t]=true;                                          //将t加入集合U中
            for(int j=1;j<=n;j++) {                             //更新lowcost和closest
                if(!s[j]&&c[t][j]<lowcost[j]) {                 //与t相邻的顶点到U的距离小于原来到U的距离则更新
                    lowcost[j]=c[t][j];
                    closest[j]=t;
                }
            }
        }
    }

}
